#include<stdio.h>
#include<malloc.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<windows.h>

//6.1 结构体实现
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
#define MAXCHROMLENGTH 500
#define STEP 25
typedef int STATUS;
int Maze[8][8]={{0,1,0,1,0,1,0,0},
                {2,1,0,1,0,1,0,0},
                {0,1,0,1,1,1,1,1},
                {1,1,1,1,1,1,1,0},
                {1,0,0,0,1,1,0,1},
                {1,0,1,0,1,1,1,1},
                {1,0,1,0,1,0,1,2},
                {1,1,1,0,1,0,1,0}};

typedef struct NODE
{
    int x,y;
}NODE;

typedef struct NEIGHBORNODE          //节点类型
{
    NODE node;                       //节点
    struct NEIGHBORNODE* next;       //领进节点
}NEIGHBORNODE, * NEIGHBOR;           //相邻节点类型【*NEIGHBOR和下文中*PATH均为指向NEIGHBORNODE的指针】

typedef struct NEIGHBORNODE* PATH;   //路径类型

typedef struct Paths                 //路径集合类型
{
    PATH path;                       //一条路径
    struct Paths* next;              //下一条路径
}Paths, * PATHS;                     //路径集合类型【*PATHS为指向PATH的指针】

typedef struct Paths* STACK;         //定义堆栈类型，实际上也是节点链表【相邻节点链表】

typedef struct INDIVIDUAL
{
    int chrom[MAXCHROMLENGTH];
    int chromlength;
    double fitness;
}INDIVIDUAL;

//3.2.2 通用赋值函数
void Set(NODE *node1, NODE *node2)
{
    node1->x=node2->x;
    node1->y=node2->y;
}

//3.2.3 复制个体函数
INDIVIDUAL CopyIndividual(INDIVIDUAL population)
{
    INDIVIDUAL tempPopulation;
    for(int i=0;i<population.chromlength;i++){
        tempPopulation.chrom[i]=population.chrom[i];
    }
    tempPopulation.chromlength=population.chromlength;
    tempPopulation.fitness=population.fitness;
    return tempPopulation;
}

//3.7.1 判断两个九宫格是否相同、赋值
STATUS equal(NODE *node1, NODE *node2)
{
    STATUS flag = TRUE;
    if(node1->x==node2->x&&node1->y==node2->y)   return TRUE;
    else                                         return FALSE;
}

//3.7.2 显示九宫格
void PriNode(NODE node)
{
    printf("(%d,%d)",node.x,node.y);
}

void PriPath(PATH path)                     //显示路径
{
    while (path!= NULL)
    {
        if(path->next!=NULL){
            PriNode(path->node);
            printf("->");
        }
        else
        {
            PriNode(path->node);
        }
        path = path->next;
    }
    printf("\n");
}

//3.2.3 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br, NODE node)        //Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b, pb;                                  //相邻节点
    b = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //动态开辟一个相邻节点
    Set(&(b->node), &node);             //【下面两行是类型为str时的情况，其他类比】
    b->next = NULL;
    if (br == NULL)                                    //没有相邻节点的情况
    {
        br = b;                                       //node就是第一个邻居
    }
    else                                            //有相邻节点的情况
    {
        pb = br;                                      //node就是最后一个相邻节点【值在b中，头插入】
        while (pb->next)   pb = pb->next;
        pb->next = b;
    }
    return br;                                      //返回相邻节点【指针】
}

//3.2.6 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br)  //回收相邻节点空间
{
    NEIGHBOR br1 = br;                 //临时相邻变量
    while (br)                        //【遍历相邻节点】
    {
        br1 = br;
        br = br->next;                //【挨个变量赋给临时指针】
        free(br1);                  //回收单元
        return br;
    }
    return br;                      //返回NULL
}

//3.3 图可复用代码部分
//3.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
NEIGHBOR CopyNeighbors(NEIGHBOR adjacents)                       //节点集复制
{
    NEIGHBOR copynode=NULL, lastnode=NULL, head = NULL;                        //没有子节点
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        Set(&copynode->node, &adjacents->node);
        copynode->next = NULL;
        if (head == NULL)
        {
            head = copynode;                                       //第1个节点
        }
        else
        {
            lastnode->next = copynode;                             //非第1个节点：建立链接，复制子节点集
        }
        lastnode = copynode;
        adjacents = adjacents->next;                               //下一个子节点
    }
    return head;                                                 //返回头节点指针
}

//3.3.2 复制路径和路径集合
PATH CopyPath(PATH path)                               //复制一条路径，返回新路径
{
    PATH tempath;
    tempath = (PATH)CopyNeighbors((NEIGHBOR)path);       //路径与邻居节点集合相同
    return tempath;
}

PATHS CopyPaths(PATHS paths)                     //复制路径集合
{
    PATHS copynode=NULL, lastnode=NULL, head = NULL;
    while (paths)                                 //路径集合不为空
    {
        copynode = (PATHS)malloc(sizeof(Paths));   //路径节点
        copynode->path = CopyPath(paths->path);    //复制一条路径
        copynode->next = NULL;                     //复制路径初始化
        if (head == NULL)                           //第1条路径
        {
            head = copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next = copynode;
        }
        lastnode = copynode;                       //加入路径集合
        paths = paths->next;
    }
    return head;
}

//3.3.3 节点加入路径
PATH Add_A_Node_To_Path(NODE *node, PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p = (NEIGHBOR)malloc(sizeof(NEIGHBORNODE));
    Set(&p->node,node); 
    if (path == NULL)                            //第1个节点
    {
        p->next = NULL;
    }
    else                                      //非第1个节点
    {
        p->next = path;                         //加入到路径头部
    }
    path = p;                                   //路径倒序加入
    return path;                                //返回路径头部
}

//3.3.4 路径加入路径集合
PATHS Add_A_Path_To_Paths(PATH path, PATHS paths) //路径加入到路径集合中
{
    PATH copypath;
    PATHS ps = NULL, p;
    if (path == NULL)   return paths;                //没有路径
    copypath = CopyPath(path);                      //复制路径
    ps = (PATHS)malloc(sizeof(Paths));              //开辟路径集合节点
    ps->path = copypath;                            //复制的路径置入
    ps->next = NULL;
    if (paths == NULL)                               //路径集合为空
    {
        paths = ps;
    }
    else                                          //路径集合为非空，新路径节点放置最后
    {
        p = paths;
        while (p->next) p = p->next;
        p->next = ps;
    }
    return paths;
}

//3.3.5 路径进栈和所有节点进栈
PATHS Push_A_Path(PATHS stack, PATH path)     //一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    PATHS st;
    tempath = CopyPath(path);                            //复制节点
    st = (PATHS)malloc(sizeof(Paths));                   //路径节点
    st->path = tempath;                                  //置路径于栈中
    if (stack == NULL)                                   //第1条路径
    {
        st->next = stack;
    }
    else                                                //非第1条路径，已有路径
    {
        st->next = stack;
    }
    stack = st;
    return stack;
}

PATHS PushPaths(PATHS stack, PATHS paths)  //所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS p, head;
    head = CopyPaths(paths);                           //复制路径集合
    p = head;
    if (p != NULL)                                      //逐一加入栈中
    {
        while (p->next) p = p->next;
        p->next = stack;
        stack = head;
    }
    return stack;
}

//3.3.6 回收栈、回收路径和回收路径集合
STACK ClearStack(STACK stack)              //回收栈空间
{
    stack = (STACK)ClearNeighbors((NEIGHBOR)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path = (PATH)ClearNeighbors((NEIGHBOR)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS ClearPaths(PATHS paths)               //回收路径集合空间
{
    PATHS paths1 = paths;
    while (paths)                              //所有路径
    {
        paths1 = paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths = paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//3.3.7 出栈与节点
PATHS Pop_A_Node(STACK stack, NODE *node, PATH* path)  //出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    PATHS p = stack;
    PATH tempath;
    if (p != NULL)
    {
        tempath = p->path;                                //一条路径
        Set(node,&(tempath->node));
        *path = CopyPath(tempath);                         //获取路径
        stack = p->next;                                  //栈顶变化
        free(p);                                        //删除路径 
    }
    return stack;                                       //返回栈顶
}


//3.3.9 路径倒叙与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num = 0, i;
    NODE* nodes;
    PATH p = path;
    while(p)                                //统计路径节点的个数
    {
        p = p->next;
        num++;
    }
    nodes = (NODE*)malloc(num * sizeof(NODE)); //开辟一维数组
    for (i = 0, p = path; p; p = p->next, i++)         //读取路径节点置于数组中
    {
        Set(&nodes[i], &(p->node));
    }
    for (i = num - 1, p = path; p; p = p->next, i--)     //数组数据倒序置于路径中
    {
        Set(&(p->node), &nodes[i]);
    }
    free(nodes);                            //回收数组空间
}

//3.4 图求解路径实现

//3.4.0 判断节点在路径中出现的次数
int CountPath(NODE node,PATH path)
{
    PATH p=path;
    int count=0;
    while(p)
    {
        if(equal(&node,&p->node)!=0){
            count++;
            p=p->next;
        }
        else{
            p=p->next;
        }
    }
    return count;
}

//3.4.1 判断节点是否在路径中
STATUS IsInPath(NODE node, PATH path)                      //判断节点是否在路径中并返回真或假
{
    PATH p = path;
    STATUS flag = FALSE;                                    //节点是否在路径中的标识
    while (p)
    {
        if (equal(&node, &p->node) != 0)                       //node在路径中
        {
            flag = TRUE;
            break;
        }
        else                                                //node不在路径中
        {
            p = p->next;
        }
    }
    return flag;                                          //返回真/假
}

//3.4.2 删除在路径中的节点
NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents, PATH path)    //从节点集合adjacents中删除节点在路径path中的节点
{
    NEIGHBOR n1 = adjacents, n2=NULL;
    STATUS flag = FALSE;
    while (n1)                                              //遍历节点集合中的每个节点
    {
        flag = IsInPath(n1->node, path);                      //节点是否在路径中
        if (flag == TRUE)
        {
            if (n1 == adjacents)                              //待删除节点位于第一个
            {
                adjacents = n1->next;                        //下一个节点
                free(n1);                                  //删除当前节点
                n1 = adjacents;                              //其他节点
            }
            else                                           //待删除节点不在第一个
            {
                n2->next = n1->next;                         //NULL
                free(n1);                                  //删除当前节点
                n1 = n2->next;                               //NULL
            }
        }
        else
        {
            n2 = n1;                                          //下一个节点
            n1 = n1->next;
        }
    }
    return adjacents;
}

//3.4.3  相邻节点形成路径合集
PATHS FromPathsFromNodes(NEIGHBOR adjacents, PATH path, PATHS paths)   //节点集合中的每个节点（不在路径中）挨个加入路径，依次形成路径集合
{
    PATH tempath;
    adjacents = DeleteNodeInPath(adjacents, path);           //删除构成回路的节点
    while (adjacents)                                      //所有不构成回路的节点
    {
        tempath = CopyPath(path);                              //复制路径
        tempath = Add_A_Node_To_Path(&adjacents->node, tempath); //在路径中加入一个节点
        paths = Add_A_Path_To_Paths(tempath, paths);            //新路径加入路径集合
        adjacents = adjacents->next;                           //下一个节点
    }
    return(paths);                                        //返回路径集合
}

//判断当前节点在迷宫中是否合法
STATUS Judge(NODE node,int size){
    if(node.x<0 || node.x>=size)   return FALSE;
    if(node.y<0 || node.y>=size)   return FALSE;
    if(Maze[node.x][node.y]==0)    return FALSE;
    return TRUE;
}

//变换节点的位置
void Exchange(NODE *node, int hori, int vert)
{
    node->x=node->x+hori;
    node->y=node->y+vert;
}

//3.7.4 相邻节点集合的生成
NEIGHBOR ExpandNodes(NODE node, int size)
{
    NEIGHBOR adjacents = NULL;
    NODE tempnode;
    STATUS legal=FALSE;

    Set(&tempnode,&node);
    Exchange(&tempnode,-1,0);      //向左移动
    legal=Judge(tempnode,8);
    if(legal==TRUE) adjacents = Add_A_Adjacents(adjacents, tempnode);

    Set(&tempnode,&node);
    Exchange(&tempnode,1,0);      //向右移动
    legal=Judge(tempnode,8);
    if(legal==TRUE) adjacents = Add_A_Adjacents(adjacents, tempnode);

    Set(&tempnode,&node);
    Exchange(&tempnode,0,-1);      //向上移动
    legal=Judge(tempnode,8);
    if(legal==TRUE) adjacents = Add_A_Adjacents(adjacents, tempnode);

    Set(&tempnode,&node);
    Exchange(&tempnode,0,1);      //向下移动
    legal=Judge(tempnode,8);
    if(legal==TRUE) adjacents = Add_A_Adjacents(adjacents, tempnode);

    return adjacents;
}

//3.7.5 长度计算
long int LengthOfPath(PATH path)
{
    long int count=1;
    while(path!=NULL)
    {
        path = path->next;
        count++;
    }
    return count;
}

//3.7.6 评估函数
float Evaluate(NODE *node1,NODE *node2)
{
    int i,j;
    double res=0;
    //res=sqrt((node1->x-node2->x)*(node1->x-node2->x)+(node1->y-node2->y)*(node1->y-node2->y));
    res=abs(node1->x-node2->x)+abs(node1->y-node2->y);
    return res;
}

void EvaluateIndividual(INDIVIDUAL *indi,NODE start,NODE end);

//6.1.4 对旅行商路径进行染色体编码
void Coding(PATH path,INDIVIDUAL *indi,NODE start,NODE end)
//对路径进行染色体编码 00表示向右  01表示向上  10表示向左  11表示向下
{
    int i=0;  
    EvaluateIndividual(indi,start,end);
    PATH now=path->next;
    while(now)
    {
        if(now->node.y==path->node.y+1){
            indi->chrom[i++]=0;
            indi->chrom[i++]=0;
        }
        else if(now->node.x==path->node.x-1){
            indi->chrom[i++]=0;
            indi->chrom[i++]=1;
        }
        else if(now->node.y==path->node.y-1){
            indi->chrom[i++]=1;
            indi->chrom[i++]=0;
        }
        else if(now->node.x==path->node.x+1){
            indi->chrom[i++]=1;
            indi->chrom[i++]=1;
        }
        path=path->next;
        now=now->next;
    }
    indi->chromlength=i;
}

//6.1.5 将染色体解码成旅行商路径
PATH Decoding(NODE start,NODE end,INDIVIDUAL indi)
//将染色体解码为路径 00表示向右  01表示向上  10表示向左  11表示向下
{
    NEIGHBOR adjacents = NULL;
    NODE tempnode;
    int i,j;
    int nowx=start.x;
    int nowy=start.y;
    for(i=0,j=1;j<=indi.chromlength;i=i+2,j=j+2){
        if(indi.chrom[i]==0&&indi.chrom[j]==0){        //向右
            tempnode.x=nowx;
            tempnode.y=nowy+1;
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        else if(indi.chrom[i]==0&&indi.chrom[j]==1){   //向上
            tempnode.x=nowx-1;
            tempnode.y=nowy;
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        else if(indi.chrom[i]==1&&indi.chrom[j]==0){    //向左
            tempnode.x=nowx;
            tempnode.y=nowy-1;
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        else if(indi.chrom[i]==1&&indi.chrom[j]==1){
            tempnode.x=nowx+1;
            tempnode.y=nowy;                          //向下
            adjacents = Add_A_Adjacents(adjacents, tempnode);
        }
        nowx=tempnode.x;
        nowy=tempnode.y;
        if(nowx==end.x&&nowy==end.y)     break;
    }
    return adjacents;
}

//6.4.1 计算染色体适应度函数值，即旅行商的路径
void EvaluateIndividual(INDIVIDUAL *indi,NODE start,NODE end)
//对染色体个体的适应度函数值求解
{
    int nowDist,minDist=32767;
    PATH tempath=NULL;
    tempath=Decoding(start,end,*indi);     //染色体个体解码为旅行商路径
    while(tempath){
        nowDist=Evaluate(&tempath->node,&end);
        if(nowDist<minDist)  minDist=nowDist;
        tempath=tempath->next;
    }
    indi->fitness=minDist;                 //旅行商路径长度为染色体个体的适应度函数值
}

//6.3 初始化染色体路径的染色体和种群
//6.3.1 在给定出发城市（也是终点城市）后随机初始化一条旅行商路径
PATH InitTraPath(NODE start,PATH path)
//给定旅行商起点城市形成随机路径
{
    NODE temp;
    temp.x=start.x;
    temp.y=start.y;
    int i,n;
    int allowMax=3;
    path=Add_A_Node_To_Path(&temp,path);
    for(i=0;i<STEP;i++){
        n=rand()%4;
        if(n==0){      //向右
            temp.y=temp.y+1;
            if(Judge(temp,8)){
                path= Add_A_Node_To_Path(&temp,path);
            }
            else{
                i--;
                temp.y=temp.y-1;
                continue;
            }
        }
        else if(n==1){      //向上
            temp.x=temp.x-1;
            if(Judge(temp,8)){
                path= Add_A_Node_To_Path(&temp,path);
            }
            else{
                i--;
                temp.x=temp.x+1;
                continue;
            }
        }
        else if(n==2){      //向左
            temp.y=temp.y-1;
            if(Judge(temp,8)){
                path= Add_A_Node_To_Path(&temp,path);
            }
            else{
                i--;
                temp.y=temp.y+1;
                continue;
            }
        }
        else if(n==3){      //向下
            temp.x=temp.x+1;
            if(Judge(temp,8)){
                path= Add_A_Node_To_Path(&temp,path);
            }
            else{
                i--;
                temp.x=temp.x-1;
                continue;
            }
        }
    }
    return path;
}

//6.3.2 在给定出发城市后随机初始化旅行商路径的一条染色体
void InitIndividual(NODE start,NODE end,INDIVIDUAL *indi)
{
    PATH trapath=NULL;
    trapath=InitTraPath(start,trapath);
    RevPath(trapath);
    Coding(trapath,indi,start,end);
}

//6.3.3 在给定出发城市和种群规模后随机初始化旅行商的种群路径
void InitPopulation(NODE start,NODE end,int popsize,INDIVIDUAL population[])
//给定旅行商路径的种群数量，随机初始化种群
{
    int i=0,j,k;
    srand((unsigned)time(NULL));                              //时间为随机数种子
    for(i=0;i<popsize;i++)                                    //初始化个体
    {
        InitIndividual(start,end,&population[i]);                //随机初始化路径的染色体个数
        //Sleep(10);                                          //时间延迟，产生不同随机数
    }
}

//6.4 路径染色体适度值的求解


//6.4.2 用来计算旅行商路径种群每个个体的适度值函数值
void EvaluatePopulation(int popsize,INDIVIDUAL population[],NODE start,NODE end)
//对种群每个个体适应度函数值的求解
{
    int i;
    for(i=0;i<popsize;i++)
    {
        EvaluateIndividual(&population[i],start,end);    //对每条染色体个体适应度函数的求解
    }
}

//6.5 路径染色体个体的有效性
STATUS Efficent(NODE start,NODE end,INDIVIDUAL indi)           //判断路径个体有效性
{
    STATUS flag=TRUE;
    PATH path;
    int i,j,k=0,count;
    path=Decoding(start,end,indi);
    while(path){
        if(Judge(path->node,8)==FALSE){
            flag=FALSE;
            //printf("%d %d不满足条件\n",path->node.x,path->node.y);
        }
        path=path->next;
    }
    return flag;
}

//6.6 遗传算子
//6.6.1 选择算子：从路径种群中采用轮盘赌选择法来选取新种群
void SelectOperator(int popsize,INDIVIDUAL population[])
//选择算子：从当前路径染色体种群population中采用轮盘赌选择法来选择个体进而形成新种群
{
    int i,j;
    double p,sum;                                                  //p存放随机概率，sum存放个体适应率和累计适应率
    double *ps;                                                    //当代种群染色体个数的适应率
    INDIVIDUAL *newpopulation;                                     //新种群
    ps=(double*)malloc(popsize*sizeof(double));                    //开辟新路径染色体种群对应的概率空间
    newpopulation=(INDIVIDUAL*)malloc(popsize*sizeof(INDIVIDUAL));
    for(sum=0,i=0;i<popsize;i++)
    {
        sum+=population[i].fitness;                                //sum存放种群适应值总和
    }
    for(i=0;i<popsize;i++)
    {
        ps[i]=population[i].fitness/sum;                           //路径染色体个体的概率
    }
    for(sum=0,i=0;i<popsize;i++)   sum+=1-ps[i];                   //路径染色体个体的概率之和
    for(i=0;i<popsize;i++)         ps[i]=(1-ps[i])/sum;            //路径染色体个体概率非新概率
    for(i=1;i<popsize;i++)         ps[i]+=ps[i-1];                 //新概率构成轮盘
    for(i=0;i<popsize;i++)                                         //for循环采用轮盘赌选择法，选择popsize个个体
    {
        p=rand()%1000/1000.0;                                      //得到千分位小数的随机数
        for(j=0;ps[j]<p;j++);                                      //转动轮盘
        newpopulation[i]=population[j];                            //选出一个数暂存于newpopulation中
    }
    for(i=0;i<popsize;i++)
    {
        population[i]=newpopulation[i];                             //更新种群population
    }
    free(ps);                                                       //回收数据单元
    free(newpopulation);
}

void CrossoverOperator(int popsize,INDIVIDUAL population[],double pc,NODE start,NODE end){
    //交叉算子
    int i,j,*index = NULL,point,temp,count;
    double p;
    index = (int *)malloc(popsize*sizeof(int));      //形成一维数组
    for(i = 0; i < popsize; i++)  index[i] = i;       //初始化数组index[],种群索引
    for(i = 0; i < popsize; i++){                     //打乱种群顺序
        point = rand()%(popsize-1);
        temp = index[i];
        index[i] = index[point+1];
        index[point+1] = temp;
    }
    i = 0;
    while (i < popsize-1)
    {
        count=0;
        p = rand()%1000/1000.0;
        if(p < pc)                 //根据概率选取第i条染色体
        {
            LOOP:
            point = rand()%(population[i].chromlength-1)+1;
            for(j = point;j < population[i].chromlength; j++){
                temp = population[index[i]].chrom[j];      //从交叉点逐位进行交换
                population[index[i]].chrom[j] = population[index[i+1]].chrom[j];
                population[index[i+1]].chrom[j] = temp;
            }
            if(!Efficent(start,end,population[index[i]]) || !Efficent(start,end,population[i+1])){
                for(j = point;j < population[i].chromlength; j++){
                    //恢复原有个体
                    temp = population[index[i]].chrom[j];      //从交叉点逐位进行交换
                    population[index[i]].chrom[j] = population[index[i+1]].chrom[j];
                    population[index[i+1]].chrom[j] = temp;
                }
                count++;
                if(count>2){
                    i+=2;
                    continue;
                }
                goto LOOP;   
            }
        i += 2;                  //索引相邻两个体
        }
    }         
}

   void MutateOperator(int popsize,INDIVIDUAL population[],double pm,NODE start,NODE end){
    //变异算子
    int i,j,count;
    double p ;
    INDIVIDUAL indi;       //染色体个体
    i = 0;
    while (i < popsize)
    {
        count=0;
        LOOP:
        indi = CopyIndividual(population[i]);
         for(j = 2; j < population[i].chromlength-1; j++){
            p = rand()%1000/1000.0;             //随机概率
            if(p < pm) indi.chrom[j] = (indi.chrom[j] == 0) ? 1 : 0;          //根据编译概率进行0和1变换
         }
         if(Efficent(start,end,indi) == FALSE){
            if(count>2){
                i++;
                continue;
            }
            goto LOOP;         //变异后旅行商路径无效
         }
         population[i] = indi;
         i++;                                                                 //下一条染色体个体
    }
    
}

//6.6 新一代染色体群体的生成和最优染色体个数
//6.6.1 在路径种群中通过遗传算子产生新种群
void GenerateNextPopulation(int popsize,INDIVIDUAL population[],double pc,double pm,NODE start,NODE end)
//通过遗传算子生成下一代群体
{
    SelectOperator(popsize,population);                     //选择生成群体population
    CrossoverOperator(popsize,population,pc,start,end);   //交换生成群体population
    MutateOperator(popsize,population,pm,start,end);      //变异生成群体population
}

//6.6.2 从路径种群中选取最优(路径最短)的路径染色体，更新迄今为止最优的路径染色体
void GetBestIndividual(int popsize,INDIVIDUAL population[],INDIVIDUAL *bestindividual,INDIVIDUAL *currentbestindividual)
//*bestindividual为当前种群中最优个体，*currentbestindividual为程序运行不断进化迄今为止最优个体
//从路径染色体种群population[]中求最优个体
{
    int i;
    *bestindividual=population[0];                             //默认种群中第0个个体为最优个体
    for(i=1;i<popsize;i++)                                     //种群中的其他个体
    {
        if(population[i].fitness<=bestindividual->fitness)     //依次比较，找出最优个体
        {
            *bestindividual=population[i];                     //更新种群中的最优个体
        }
    }
    if(bestindividual->fitness<currentbestindividual->fitness)
    //当前代最优个体bestindividual与迄今为止最优个体currentbestindividual进行比较
    {
        *currentbestindividual=*bestindividual;                 //更新迄今为止最优个体
    }
}

//6.7 遗传进化
void GA(NODE start, NODE end,int popsize,double pc,double pm,int generation,INDIVIDUAL *currentbestindividual)
//遗传进化过程
{
    INDIVIDUAL *population,bestindividual,oldbestindividual;                             //种群、最优个体                                                                 //明文路径
    int i;
    population=(INDIVIDUAL *)malloc(popsize*sizeof(INDIVIDUAL));                         //分配种群单元
    InitPopulation(start,end,popsize,population);                                 //初始化种群
    bestindividual=population[0];                                                        //默认初始种群中的最优个体
    for(i=1;i<popsize;i++)
    {
        if(population[i].fitness<bestindividual.fitness)                                //依次比较找出最优个体
        {
            bestindividual=population[i];                                               //更新初始种群中最优个体
        }
    }
    *currentbestindividual=bestindividual;                                              //初始种群中的最优个体为进化过程迄今为止最优个体
    oldbestindividual=bestindividual;                                                   //迄今为止最优个体为过往最优个体
    i=0;
    while(i<generation)                                                                 //连续进化generation代，最优个体不变
    {
        GenerateNextPopulation(popsize,population,pc,pm,start,end);                    //产生新一代种群【选择、交叉、变异】
        EvaluatePopulation(popsize,population,start,end);                              //评估新一代种群
        GetBestIndividual(popsize,population,&bestindividual,currentbestindividual);    //获取种群中最优个体和迄今为止最优个体
        if(fabs(currentbestindividual->fitness - oldbestindividual.fitness)<1e-5)   i++;  //连续进化的代数统计
        else 
        {
            oldbestindividual=*currentbestindividual;                                   //更新过往最优个体
            i=0;                                                                        //连续进化的代数计数归零
        }
    }
    //Sleep(500);
}

//3.7.6 输出迷宫图
void PriMaze(PATH path,NODE start,NODE end)
{
    int temp[8][8];
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            temp[i][j]=Maze[i][j];
        }
    }
    while (path!= NULL)
    {
        temp[path->node.x][path->node.y]=3;
        path = path->next;
    }
    temp[start.x][start.y]=2;
    temp[end.x][end.y]=2;
    printf("=============\n");
    printf("图例说明: @:路径 ■:障碍 #:起终点 -:可行域\n");
    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(temp[i][j]==3)  printf(" @ ");
            else if(temp[i][j]==0)  printf(" ■ ");
            else if(temp[i][j]==2)  printf(" # ");
            else if(temp[i][j]==1)  printf(" - ");
        }
        printf("\n");
    }
}

//3.7.M 主程序
int main()
{
    STATUS flag;
    PATH path=NULL;
    INDIVIDUAL currentbestindividual;  //当前最优个体
    NODE start={1,0},end={6,7};
    printf("Search from");
    PriNode(start);
    printf("to");
    PriNode(end);
    double pc=0.4;                    //交叉率为0.25-0.99
    double pm=0.05;                   //变异率为0.001-0.01
    int popsize=15;                   //种群数
    int generation=2000;               //连续进化最优个体，代数不变
    int count=10;                     //求解次数
    for(int i=0;i<count;i++)          //求解count次
    {
        GA(start,end,popsize,pc,pm,generation,&currentbestindividual);    //智能算法——遗传算法求解
        printf("Resule Path:");
        path=Decoding(start,end,currentbestindividual);                   //解码为路径
        flag=IsInPath(end,path);
        PriPath(path);
        printf("Step=%ld,Status=%d\n",LengthOfPath(path)-1,flag);
        PriMaze(path,start,end);
        printf("=============\n");
    }
    ClearPath(path);
    return 0;
}